云平台上基于关键路径截取的有向无环图应用调度算法

针对云平台上有向无环图科学应用执行容易产生虚拟机资源过剩、资源使用率低及费用虚高的问题,给出一种基于关键路径截取的有向无环图应用调度算法。该算法采取关键路径截取技术,循环找出最晚完成的未分配任务,从该任务出发,在所有未分配任务构成的图中找出最大连通子图,并计算该子图的关键路径,然后将关键路径上的任务集调度到性能匹配的虚拟机上执行;同时通过任务回填技术充分利用虚拟机的空闲时间槽,提高资源使用率。实验结果表明,在云计算平台上,该算法不仅能够在截止时间内完成有向无环图科学应用,而且可以提高资源使用率,有效减少完成该应用所需整体费用。     

图的色数与亏格的相对独立性

本文先证明如下定理:“对于每一个非负整数p,亏格为p 的图的色数可以是任意整数m, 2≤m≤[7+(1+48p/2)].”然后,据此定理得结论:当m≥3,要找到m—色图的充分必要条件基本上是不可能的,即使不说根本不可能。     

系统状态方程的信流图描述

本文从基本概念出发,结合两个具体电路讨论如何用信流图建立系统标准状态方程的方法。     

融合图嵌入的光滑主成分分析网络图像识别算法

主成分分析网络(principal component analysis network, PCANet)是一种简单的深度学习算法,在图像识别领域具有优秀的性能。将图嵌入思想融入PCANet,提出一种新的图像识别算法光滑主成分分析网络(Smooth-PCANet)。为了验证Smooth-PCANet算法的有效性,在人脸、手写体字符以及图片等不同数据集上构建实验,并将Smooth-PCANet与多种基于深度学习的图像识别算法作了对比。实验结果证明,Smooth-PCANet算法比PCANet获得了更高的识别性能,并且更有效地避免了过拟合,在小样本训练时具有显著优势。     

并行程序运行故障原因识别

高性能计算系统的复杂性和规模的不断增长使得系统的平均无故障时间越来越短,因此系统的硬软件故障导致并行程序运行出错的概率随之增加。此外,并行程序本身可能存在的编程错误也会导致运行出错。由于处理上述两类故障原因的措施迥异,所以在程序运行出现故障时,用户需要关注故障原因的类别。针对这一问题,设计和实现了一种基于作业管理系统Slurm的并行程序运行故障原因识别系统。通过对Slurm进行扩展,监控作业状态,重提交和重运行作业。根据作业运行结果,区分故障原因类别。故障注入方式进行的实验表明,该系统具有较高的识别准确率。     

高性能计算和数据中心融合网络研究综述

随着高性能计算、大数据处理、云计算和人工智能计算呈融合发展趋势,高性能计算网络和数据中心网络的融合网络成为互连网络发展的重要趋势。分析当前融合网络研究现状;针对当前最具代表性的融合网络进行详细阐述,全面展示该领域的最新技术和动态;提出融合网络面临的技术挑战;基于技术挑战对融合网络的发展趋势进行展望,包括融合网络协议栈设计中融合与分化并存、基于在网计算实现融合网络性能加速、面向新兴应用需求优化融合网络性能。     

大型卫星地面站故障诊断的增强分层有向图方法

为了解决传统分层有向图模型在卫星地面站故障诊断面临的问题,提出了基于增强分层有向图模型的故障诊断方法。在建模过程中,考虑到卫星地面站故障征兆多、建模复杂,依据各设备工作状态的故障传播方式合并同类节点,以减小模型规模;同时,在模型中加入节点有效性使能函数,克服传统分层有向图模型中设备主备切换导致系统结构发生改变时需要重新建模的问题。在故障诊断推理过程中,采用反向回溯和正向推理相结合的方法减小故障源搜索空间,并基于各节点被搜索次数给出故障概率,提高诊断效率。以北斗卫星无线电测定业务地面站为例对单故障和多故障报警场景下的故障诊断方法进行了验证。结果表明,基于增强分层有向图模型的故障诊断方法可以提高故障诊断的准确率和全面性。     

动态拓扑图的卫星网络可视化方法

针对高度动态变化的卫星网络,提出一种基于动态拓扑图的可视化方法。动态拓扑图可视化的难点在于如何保持动态可视化过程中的稳定性,从而使用户容易地感知到网络中所发生的拓扑变化。根据卫星网络的动态变化特点,构建连续的动态拓扑图模型;设计一种保持布局稳定性的策略,并基于力引导思想提出一种动态拓扑图布局算法;以Iridium系统为典型实例,验证本文的可视化方法的合理性和可行性。实验表明,该方法能够以清晰的可视化图像支持用户对卫星网络动态拓扑的感知和理解。     

面向复杂几何模型的多级并行四面体网格生成算法

高性能计算机的快速发展为数值模拟提供了必需的硬件环境,数值模拟领域对网格的需求已高达数十亿到数百亿量级,而网格生成作为数值模拟的重要一环,其发展则相对滞后,很难满足并行数值模拟求解器对大规模网格的需求。本文面向复杂几何模型提出一种多级并行四面体网格生成算法,该算法首先基于模型的几何特征建立网格的尺寸场,并基于尺寸场和几何实体间的邻接关系对几何实体进行分组,将分组后的几何实体分配到不同的计算节点,在计算节点间采用前沿推进法实现三角形面网格的并行生成,然后在计算节点内对三角形面网格进行二级区域分解,将分解后的子网格分配到各进程中,最后在进程内采用多线程并行方法实现四面体网格的并行生成。通过实际应用三峡大坝模型进行验证,该算法具有良好的并行效率和可扩展性,可以在数千处理器核上实现十亿规模高质量四面体网格的并行生成。     

New results on rendezvous search on the interval

In a rendezvous search problem, two players are placed in a network and must try to meet each other in the least possible expected time. We look at rendezvous search on a discrete interval in which the players are initially placed using independent draws (usually assumed to be from the same distribution). Some optimal solutions are known if this distribution is uniform, and also for certain other special types of distribution. In this article, we present two new results. First, we characterize the complete set of solutions for the uniform case, showing that all optimal strategies must have two specific properties (namely, of being swept and strictly geodesic). Second, we relate search strategies on the interval to proper binary trees, and use this correspondence to derive a recurrence relation for solutions to the symmetric rendezvous problem for any initial distribution. This relation allows us to solve any such problem computationally by dynamic programming. Finally, some ideas for future research are discussed. © Wiley Periodicals, Inc. Naval Research Logistics 60: 454–467, 2013